1. Field of the Invention
The present invention relates to computer memory architecture, and, in particular, to the architecture of content-addressable memory.
2. Description of the Related Art
Content-addressable memory (CAM) is a particular type of random access memory (RAM) that can be written to and read from like a standard RAM, but can also be searched for specific content. In particular, CAM memory can be searched for a set of consecutive CAM cells that have a specified string of data values. Typically, the size of the search string corresponds to the word length of the CAM memory, and the search is performed in parallel in all data words to output, if the string is found, the address of the CAM word where the string exists. In a typical CAM design, if the string exists in two or more CAM words, the search will identify only one of them (e.g., the one with the lowest address).
FIG. 1 shows a schematic diagram of the layout for a prior-art CAM memory 100 supporting 1024 72-bit data words. CAM memory 100 consists of a two-dimensional array of 72 columns and 1024 rows of CAM cells 102. For each column of cells in the array, CAM memory 100 also has a set of column support circuitry 104. Analogously, for each row of cells in the array, CAM memory 100 has a set of row support circuitry 106. Those skilled in the art will understand that the column and row support circuitry includes sense amps, input latches, output drivers, and other components needed to access the array of cells.
FIG. 2 shows a schematic diagram of the cell architecture of CAM memory 100 of FIG. 1. In particular, FIG. 2 shows two vertically adjacent CAM cells 102 from one of the columns of the array of CAM memory 100 of FIG. 1. Each CAM cell comprises a conventional static RAM (SRAM) core cell 202 with six transistors: two cross-coupled inverters as a latch element and two access transistors for reading and writing. Each CAM cell also has XOR logic 204 comprising four additional devices (e.g., n-FETS) to support the content-searching function.
Access to each individual cell 102 is provided via corresponding word line WL, match line ML, true and complement bit lines BLT and BLC, and true and complement search-data lines MT and MC, where each line is either pre-charged high and active low or pre-charged low and active high, depending on the particular design. As indicated in FIGS. 1 and 2, each horizontal word line WL and each match line ML are shared by all of the cells in the corresponding row. Similarly, each vertical bit line BLT/BLC and each search-data line MT/MC are shared by all of the cells in the corresponding column.
Data bits are written into the individual cells of a word in parallel, by activating the word line WL corresponding to the appropriate row and pulsing the appropriate bit line BLT or BLC for each column. Pulsing bit line BLT stores a 1 in the corresponding cell, while pulsing bit line BLC stores a 0.
Similarly, data bits are read from the individual cells of a word in parallel, by activating the word line WL corresponding to the appropriate row. Each cell in that row will then drive either the BLT bit line or the BLC bit line depending on the value stored in the cell. If the stored bit value is 1, then the cell will drive the BLT bit line; otherwise, the cell will drive the BLC bit line indicating a stored bit value of 0.
Content searching is achieved using the match lines ML and the search-data lines MT and MC. In particular, one search-data line is driven active for each column in the array depending on the corresponding data bit in the search string. If the corresponding data bit in the search string is a 1, then the true search-data line MT is driven; otherwise, the complement search-data line MC is driven corresponding to a data bit of 0. If any cell in a word does not match its search input bit, then the corresponding match line ML will indicate that no match exists for that word. If, however, each bit in the search string matches each corresponding bit in a particular row of the array, then the corresponding match line ML will indicate that a match has been found at that word. Depending on the particular design, the pre-charge state of each match line will correspond to either a match condition or a no-match condition. In either case, each match line will be driven as necessary to indicate the appropriate search result for that word.
As shown in FIG. 1, CAM memory 100 requires only two horizontal lines (i.e., word line WL and match line ML) for each row of CAM cells 102, but four vertical lines (i.e., bit lines BLT and BLC and search-data lines MT and MC) for each column of CAM cells 102 in the array. As indicated in FIG. 1, in order to provide column support circuitry for four different vertical lines and have the pitch of the layout for that column support circuitry match the pitch of the cells, the height of that layout area must typically be relatively large. The narrowness of the available pitch results in a relatively inefficient layout for this column support circuitry.
Another problem with conventional CAM architecture, such as that of CAM memory 100 of FIGS. 1 and 2, relates to bit-line loading. Each row in a CAM memory device contributes capacitance and resistance to the bit lines used for reading and writing data bits from and to the individual cells, which increased impedance in turn decreases the speed of that data access. When a CAM memory has a relatively large number of words, such as the 1024 words of CAM memory 100, the bit-line loading resulting from all that impedance can result in unacceptably low CAM performance. For some applications, CAM performance requirements limit the size of the CAM cell array to less than 1024 rows (e.g., a maximum of 512 rows). As a result, the size of CAM memory, in terms of the number of words supported, may be limited for such applications.